package d2;
import java.util.*;

public class Day11 {

    public static void main(String[] args) {


//        List<List<Integer>>  ret = new LinkedList<>();
//        List<Integer>  tmp1 = new LinkedList<>();
//        tmp1.add();
//        tmp1.add();
//        tmp1.add();
//        ret.add(tmp1);
//        List<Integer>  tmp2 = new LinkedList<>();
//        tmp2.add();
//        tmp2.add();
//        tmp2.add();
//        ret.add(tmp2);
//        List<Integer>  tmp3 = new LinkedList<>();
//        tmp3.add();
//        tmp3.add();
//        tmp3.add();
//        ret.add(tmp3);


        //int[][] nums = {{},{},{},{},{}};


//        int a = 10;
//        int b =20;
//        System.out.println(Math.max(a,b));
//        int max = Integer.MAX_VALUE;
//        int min = Integer.MIN_VALUE;

//        String s ="999";
//        int a = Integer.parseInt(s);
//        System.out.println(a);



//        char ch = 'A';
//        int num = ch;
//        System.out.println(num+1);
    }

    public static void main3(String[] args) {
        List<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        String s = String.valueOf(7);
        System.out.println();
        //Collections.sort(list,(a,b)-> b-a);
        Collections.sort(list,(a,b)->{
            return b-a;
        });
        System.out.println();
        for(int x:list) System.out.println(x);
        //int[] a = {3,30,34,5,9};
        int[] a = {1000000000, 1000000000};
        //largestNumber(a);
    }
    public String largestNumber(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                String t1 = String.valueOf(nums[j])+String.valueOf(nums[j+1]);
                String t2 = String.valueOf(nums[j+1])+String.valueOf(nums[j]);
                if(t2.compareTo(t1)>0) {
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
        String ret = new String();
        for(int i=0;i<n;i++) {
            ret += String.valueOf(nums[i]);
        }
        if(ret.charAt(0)=='0') return "0";
        return ret;
    }





    public static void main1(String[] args) {
        minCut("aab");
    }
    //分割回文串Ⅱ
    public static int minCut(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i=n-1;i>=0;i--)
            for(int j=i;j<n;j++) {
                if(s.charAt(i)==s.charAt(j)) {
                    if(i==j) dp[i][j]=true;
                    else if(i+1==j) dp[i][j]=true;
                    else dp[i][j]=dp[i+1][j-1];
                }
            }
        int[] vis = new int[n];//将字符串[0,i]分割成回文的最小操作次数
        for(int i=1;i<n;i++) {
            if(dp[0][i]) vis[i]=0;
            else {
                //0-i不是回文串
                int minV = Integer.MAX_VALUE;
                for(int j=i;j>0;j--) {
                    if(dp[j][i]) minV = Math.min(minV,vis[j-1]+1);
                }
                vis[i]=minV;
            }
        }
        return vis[n-1];
    }
}
